When developing computer software, developers often use a high-level language, such as C or the like, as a programming language. Source code written in a high-level language may be converted by a compiler into object code that is executable by a processor. Many compilers provide not only a function of checking syntax errors in source code, but also a function of checking semantic errors which lead to an improper operation such as memory access violation and the like.
A semantic error may occur in association with a reference to an array. An array is a data structure capable of storing multiple data elements. The entire array is specified by a variable (an array variable), and each data element in the array is specified by an index. The array is often used in loop processing for performing similar operations on multiple data elements. An example of a semantic error associated with a reference to an array is as follows. An array is referenced using an index value outside the declared range, so that a wrong memory area is accessed. Another example is as follows. When an operation of storing a data element by specifying an index value and an operation of acquiring a data element by specifying the same index value are parallelized, the execution order of the two operations is not controlled, so that the intended processing results might not be achieved.
If it is obvious from source code that an array reference causes an improper operation, the compiler may display an error message, and may stop compilation without generating object code (static checking at compilation time). On the other hand, if it is not known at compilation time whether an array reference causes an improper operation, such as when an array reference is dependent on a parameter value which is determined at run time, the compiler often inserts check code into the object code. The check code checks whether the processing may proceed, based on the parameter value at run time and the like, before an improper operation occurs (for example, before referring to an array using an index value outside the declared range) (dynamic checking at run time).
For example, there has been proposed a method of checking improper use of index. According to this checking method, a compiler acquires source code in which a loop variable I for controlling the number of iterations of a loop varies from an initial value M to a final value N, and in which an array A is referenced in the loop by using an index I×4−3. The initial value M and the final value N are parameters whose values are determined at run time. Thus, the compiler generates a subroutine for checking whether the index value when the loop variable I=the initial value M and the index value when the loop variable I=the final value N are within the declared range. Then, the compiler generates object code in which this subroutine is called immediately before the loop.
Further, for example, there has been proposed an optimization method using a compiler. According to this optimization method, a compiler determines whether two operations are independent (neither uses the result of the other operation). If the two operations are determined to be independent, an attempt is made to parallelize the two operations. For determining the independence, the compiler detects a loop written with an array X, a loop variable J, and constants a1, a2, b1, and b2. It is assumed that, in this loop, a reference to the array X using an index a1×J+b1 and a reference to the array X using an index a2×J+b2 are close. Then, the compiler determines whether (a1−a2)×J+(b1−b2)=0 holds for an arbitrary loop variable J, and thereby examines the likelihood that the two indices refer to the same data element.
Please see, for example, Japanese Laid-open Patent Publication (JP-A) No. 2-148330; Japanese Laid-open Patent Publication (JP-A) No. 5-197563; and Alexander Schrijver, “Theory of Linear and Integer Programming”, John Wiley & Sons, pp. 155-157, Jun. 4, 1998.
However, the methods disclosed in JP-A No. 2-148330 and JP-A No. 5-197563 are applicable to a relatively simple array reference in which each of the initial value and the final value of the loop variable is expressed by a constant or a single parameter and in which the index of the array is expressed by a primary expression including the single loop variable. It is difficult to apply the methods disclosed in JP-A No. 2-148330 and JP-A No. 5-197563 to a relatively complex array reference in which the loop is a multi-loop including multiple loop variables, or in which the definition of the variation range of the loop variable is complex. That is, with these methods, it is not always possible to check, for an arbitrary loop, whether there is improper use of index, whether parallelization is possible, or the like. Accordingly, the items that may be verified before loop processing are limited.